/**************************************************************************************************
* Title: SumOrderedArray.inl
* Author: Gael Huber
* Description: Maintains a standard array that is self-ordering
**************************************************************************************************/

/**************************************************************************************************
* Defalt constructor (default capacity is 4)
**************************************************************************************************/
template <typename Type>
inline OrderedArray<Type>::OrderedArray(void)
	: count(0), capacity(4), data(new Type[4])
{ }

/**************************************************************************************************
* Copy constructor
**************************************************************************************************/
template <typename Type>
inline OrderedArray<Type>::OrderedArray(const OrderedArray<Type>& rhs)
	: count(rhs.getCount()), capacity(rhs.getCapacity())
{
	// Declare space for data
	data = new Type[capacity];

	// Iterate through and fill the array
	for(int i(0); i < count; ++i) {
		data[i] = rhs[i];
	}
}

/**************************************************************************************************
* Destructor
**************************************************************************************************/
template <typename Type>
inline OrderedArray<Type>::~OrderedArray(void) {
	if(data)	delete[] data;
}

/**************************************************************************************************
* Assignment operator
**************************************************************************************************/
template <typename Type>
OrderedArray<Type>& OrderedArray<Type>::operator=(const OrderedArray<Type>& rhs) {
	// Self-assignment prevention
	if(this == &rhs)
		return *this;

	// Delete any existing data
	if(data)	delete[] data;

	// Set counts and allocate new space for array
	count = rhs.getCount();
	capacity = rhs.getCapacity();
	data = new Type[capacity];

	// Populate the array
	for(int i(0); i < count; ++i) {
		data[i] = rhs[i];
	}

	return *this;
}

/**************************************************************************************************
* Equivalence operator
**************************************************************************************************/
template <typename Type>
bool OrderedArray<Type>::operator==(const OrderedArray<Type>& rhs) const {
	// Check length
	if(count != rhs.getCount())
		return false;

	// Iterate through and return false if not equal
	for(int i(0); i < count; ++i) {
		if(data[i] != rhs[i])
			return false;
	}

	return true;
}

/**************************************************************************************************
* Non-equivalence operator
**************************************************************************************************/
template <typename Type>
bool OrderedArray<Type>::operator!=(const OrderedArray<Type>& rhs) const {
	// Check length
	if(count != rhs.getCount())
		return true;

	// Iterate through and return true if anything is not equal
	for(int i(0); i < count; ++i) {
		if(data[i] != rhs[i])
			return true;
	}

	return false;
}

/**************************************************************************************************
* Insert an element into the ordered list
**************************************************************************************************/
template <typename Type>
void OrderedArray<Type>::insert(const Type& val) {
	// First, find out whether we would need to grow the array
	if(count + 1 > capacity)
		grow();

	// We must now find the insertion point
	int insert = 0;
	for(int i = 0; i < count; ++i) {
		if(data[i] > val)
			i = count;
		else
			++insert;
	}

	// Shift everything past the insertion point to the right one
	for(int i = count - 1; i >= insert; --i) {
		data[i + 1] = data[i];
	}

	// Insert the data
	data[insert] = val;
	++count;
}

/**************************************************************************************************
* Given an index and the number of elements to remove, splice elements from the array
**************************************************************************************************/
template <typename Type>
void OrderedArray<Type>::splice(int index, int length) {
	// Cap length
	if(index + length > count - 1)
		length = count - index - 1;

	// Remove elements
	for(int i = index + length; i < count; ++i) {
		data[i - length] = data[i];
	}

	// Decrement length
	count -= length;
}

/**************************************************************************************************
* Removes one instance of the given value if it exists
**************************************************************************************************/
template <typename Type>
void OrderedArray<Type>::splice(const Type& val) {
	// Find the element
	int index = find(val);

	if(index > -1) {
		--count;
		for(int i = index; i < count; ++i) {
			data[i] = data[i + 1];
		}
	}
}

/**************************************************************************************************
* Removes all instances of a given value from the array
**************************************************************************************************/
template <typename Type>
void OrderedArray<Type>::splice_all(const Type& val) {
	// See whether any instances exist
	int index = find(val);

	if(index > -1) {
		// Find the first index
		while(index > 0 && data[index] == data[index - 1])
			--index;

		int endIndex = index;
		while(endIndex < count && data[endIndex] == data[endIndex + 1])
			++endIndex;

		// Find the difference and shift values
		int diff = endIndex == index ? 1 : endIndex - index;
		count -= diff;
		for(int i = index; i < count; ++i) {
			data[i] = data[i + diff];
		}

	}
}

/**************************************************************************************************
* Find an element. If the element is not found, return -1
**************************************************************************************************/
template <typename Type>
int OrderedArray<Type>::find(const Type& val) const {
	int min = 0;
	int max = count - 1;
	int mid = 0;
	while(max > min) {
		mid = (min + max) / 2;
		if(val > data[mid])
			min = mid + 1;
		else if(val < data[mid])
			max = mid - 1;
		else
			return mid;
	}

	return -1;
}

/**************************************************************************************************
* Accessor for the array
**************************************************************************************************/
template <typename Type>
inline Type& OrderedArray<Type>::operator[](int index) const {
	return data[index];
}

/**************************************************************************************************
* Returns the current size of the array
**************************************************************************************************/
template <typename Type>
inline int OrderedArray<Type>::getCount(void) const {
	return count;
}

/**************************************************************************************************
* Capacity
**************************************************************************************************/
template <typename Type>
inline int OrderedArray<Type>::getCapacity(void) const {
	return capacity;
}

/**************************************************************************************************
* Return an iterator at the start of the array
**************************************************************************************************/
template <typename Type>
inline typename OrderedArray<Type>::Iterator OrderedArray<Type>::begin(void) const {
	return Iterator(data);
}

/**************************************************************************************************
* Return an iterator at the end of the array
**************************************************************************************************/
template <typename Type>
inline typename OrderedArray<Type>::Iterator OrderedArray<Type>::end(void) const {
	return Iterator(data + count);
}

/**************************************************************************************************
* Grow the array
**************************************************************************************************/
template <typename Type>
void OrderedArray<Type>::grow(void) {
	// Increase capacity and create a pointer to the new array
	capacity *= 2;
	Type* nPointer = new Type[capacity];

	// Iterate through the old array and copy the data
	for(int i(0); i < count; ++i) {
		nPointer[i] = data[i];
	}

	// Delete the old array
	delete[] data;

	// Assign this array to point to the new array
	data = nPointer;
}